package 算法.力扣;

/**
 * @author: 谢君臣
 * @create: 2020-09-08 19:15
 * @founction: XXXX
 */

public class dfs {

    public static void main(String[] args) {

        char[][] temp = new char[][]{
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        String word = "SEE";
//        exist(temp, word);
    }

    public boolean exist(char[][] board, String word) {
        if (word==null) return true;
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i=0;i<board.length;i++) {
            for (int j=0;j<board[0].length;j++) {
                if (board[i][j]==word.charAt(0) && this.search(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    public boolean search(char[][] board, String word, int i, int j, int index, boolean[][] visited) {
        if (index>=word.length()) return true;
        if (i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]!=word.charAt(index) || visited[i][j]) {
            return false;
        }
        visited[i][j] = true;
        if (this.search(board,word,i-1,j,index+1,visited) ||
                this.search(board,word,i,j+1,index+1,visited) ||
                this.search(board,word,i+1,j,index+1,visited) ||
                this.search(board,word,i,j-1,index+1,visited) )
            return true;
        visited[i][j] = false;
        return false;
    }
}
